/*
 * Copyright (c) 2023-2024 dragonSaberCaptain.All rights reserved.
 * 当前项目名:wisdom-parent
 * 当前模块名:common-tools
 * 当前文件的权限定名:com.wisdom.tools.algorithm.AStar
 * 当前文件的名称:AStar.java
 * 当前文件的类名:AStar
 * 上一次文件修改的日期时间:2024/1/19 下午1:31
 *
 */

package com.wisdom.tools.algorithm;

import lombok.Data;
import lombok.experimental.Accessors;
import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * A*算法示例，用于寻找从起点到终点的最短路径。
 *
 * @author captain
 * @version 1.0
 * @projectName wisdom-parent
 * @packageName com.wisdom
 * @dateTime 2023/12/12 16:31 星期二
 */
@Slf4j
@Data
@Accessors(chain = true)
public class AStar {

    private static final int INFINITY = Integer.MAX_VALUE;

    /**
     * 寻找最短路径的方法。
     *
     * @param start 起点节点
     * @param goal  终点节点
     * @return 最短路径的节点列表，如果没有找到路径则返回null
     */
    public static List<Node> findPath(Node start, Node goal) {
        // 创建一个 open 表，用于存储待扩展的节点
        PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparingInt(Node::getF));

        // 创建一个 closed 表，用于存储已经扩展过的节点
        Set<Node> closed = new HashSet<>();

        // 将起点加入 open 表
        open.add(start);

        while (!open.isEmpty()) {
            // 从 open 表中取出 f 值最小的节点
            Node current = open.poll();

            // 如果当前节点是终点，则返回从起点到当前节点的路径
            if (current == goal) {
                return reconstructPath(current);
            }

            // 将当前节点加入 closed 表
            closed.add(current);

            // 遍历当前节点的所有邻居节点
            for (Node neighbor : current.getNeighbors()) {
                // 如果邻居节点已经在 closed 表中，则跳过
                if (closed.contains(neighbor)) {
                    continue;
                }

                // 计算到达邻居节点的代价
                int g = current.getG() + getDistance(current, neighbor);

                // 如果邻居节点不在 open 表中，或者到达邻居节点的代价更小，则更新邻居节点的 g 值和 f 值
                if (!open.contains(neighbor) || g < neighbor.getG()) {
                    neighbor.setG(g);
                    neighbor.setF(g + getHeuristic(neighbor, goal));
                    neighbor.setParent(current);
                    open.add(neighbor);
                }
            }
        }

        // 如果没有找到路径，则返回 null
        return null;
    }

    /**
     * 重构路径的方法，从终点节点回溯到起点节点。
     *
     * @param node 终点节点
     * @return 起点到终点的节点列表
     */
    private static List<Node> reconstructPath(Node node) {
        List<Node> path = new ArrayList<>();
        while (node != null) {
            path.add(node);
            node = node.getParent();
        }
        Collections.reverse(path);
        return path;
    }

    /**
     * 计算两个节点之间的距离。
     *
     * @param node1 节点1
     * @param node2 节点2
     * @return 节点1到节点2的距离
     */
    private static int getDistance(Node node1, Node node2) {
        return Math.abs(node1.getX() - node2.getX()) + Math.abs(node1.getY() - node2.getY());
    }

    /**
     * 估计从节点到终点的距离。
     *
     * @param node 节点
     * @param goal 终点
     * @return 从节点到终点的估计距离
     */
    private static int getHeuristic(Node node, Node goal) {
        return Math.abs(node.getX() - goal.getX()) + Math.abs(node.getY() - goal.getY());
    }

    public static void main(String[] args) {
        // 创建一个迷宫地图
        int[][] maze = {
                {0, 0, 0, 0, 0},
                {0, 1, 1, 1, 0},
                {0, 0, 0, 0, 0},
                {0, 1, 1, 1, 0},
                {0, 0, 0, 0, 0}
        };

        // 创建节点
        Node[][] nodes = new Node[maze.length][maze[0].length];
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[0].length; j++) {
                nodes[i][j] = new Node(i, j);
            }
        }

        // 设置节点的邻居关系
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[0].length; j++) {
                if (i > 0 && maze[i - 1][j] == 0) {
                    nodes[i][j].addNeighbor(nodes[i - 1][j]);
                }
                if (i < maze.length - 1 && maze[i + 1][j] == 0) {
                    nodes[i][j].addNeighbor(nodes[i + 1][j]);
                }
                if (j > 0 && maze[i][j - 1] == 0) {
                    nodes[i][j].addNeighbor(nodes[i][j - 1]);
                }
                if (j < maze[0].length - 1 && maze[i][j + 1] == 0) {
                    nodes[i][j].addNeighbor(nodes[i][j + 1]);
                }
            }
        }

        // 设置起点和终点
        Node start = nodes[0][0];
        Node goal = nodes[4][4];

        // 查找最短路径
        List<Node> path = findPath(start, goal);

        // 输出路径
        if (path != null) {
            for (Node node : path) {
                System.out.println("(" + node.getX() + ", " + node.getY() + ")");
            }
        } else {
            System.out.println("无法找到路径");
        }
    }

    /**
     * 节点类，表示寻路的节点。
     */
    static class Node {
        private int x;
        private int y;
        private int g;
        private int f;
        private Node parent;
        private List<Node> neighbors;

        /**
         * 构造方法，创建一个节点。
         *
         * @param x x坐标
         * @param y y坐标
         */
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
            this.g = 0;
            this.f = 0;
            this.parent = null;
            this.neighbors = new ArrayList<>();
        }

        /**
         * 获取x坐标。
         *
         * @return x坐标
         */
        public int getX() {
            return x;
        }

        /**
         * 获取y坐标。
         *
         * @return y坐标
         */
        public int getY() {
            return y;
        }

        /**
         * 获取g值，表示从起点到当前节点的实际代价。
         *
         * @return g值
         */
        public int getG() {
            return g;
        }

        /**
         * 设置g值，表示从起点到当前节点的实际代价。
         *
         * @param g g值
         */
        public void setG(int g) {
            this.g = g;
        }

        /**
         * 获取f值，表示从起点经过当前节点到终点的估计代价。
         *
         * @return f值
         */
        public int getF() {
            return f;
        }

        /**
         * 设置f值，表示从起点经过当前节点到终点的估计代价。
         *
         * @param f f值
         */
        public void setF(int f) {
            this.f = f;
        }

        /**
         * 获取父节点。
         *
         * @return 父节点
         */
        public Node getParent() {
            return parent;
        }

        /**
         * 设置父节点。
         *
         * @param parent 父节点
         */
        public void setParent(Node parent) {
            this.parent = parent;
        }

        /**
         * 获取邻居节点列表。
         *
         * @return 邻居节点列表
         */
        public List<Node> getNeighbors() {
            return neighbors;
        }

        /**
         * 添加一个邻居节点。
         *
         * @param neighbor 邻居节点
         */
        public void addNeighbor(Node neighbor) {
            neighbors.add(neighbor);
        }
    }
}
